#define _CRT_SECURE_NO_WARNINGS 1

void insert(int arr[], int length)
{
	for (int i = 0; i < length; i++)
	{
		int j = i - 1;
		int tmp = arr[i];
		while (j >= 0)
		{
			if (arr[j] > tmp)
			{
				arr[j + 1] = arr[j];
				j--;
			}
			else
			{
				break;
			}
		}
		arr[j + 1] = tmp;
	}
}

void bubbleSort(int arr[], int length)
{
	for (int i = 0; i < length; i++)
	{
		for (int j = 0; j < length - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				swap(&arr, j, j + 1);
			}
		}
	}
}

void swap(int arr[], int i, int j)
{
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}

void quickSort(int arr[], int length)
{
	quick(&arr, 0, length - 1);
}

void quick(int arr[], int start, int end)
{
	if (start >= end) return;
	int pivot = partition(&arr, start, end);
	quick(&arr, start, pivot - 1);
	quick(&arr, pivot + 1, end);
}

int partition(int arr[], int left, int right)
{
	int tmp = arr[left];
	while (left < right)
	{
		while (left < right && arr[right] >= tmp)
		{
			right--;
		}
		arr[left] = arr[right];
		while (left < right && arr[left] <= tmp)
		{
			left++;
		}
		arr[right] = arr[left];
	}
	arr[left] = tmp;
	return left;
}

void selectSort(int arr[], int length)
{
	for (int i = 0; i < length; i++)
	{
		int minIndex = i;
		for (int j = i + 1; j < length; j++)
		{
			if (arr[j] < arr[minIndex]) minIndex = j;
		}
		swap(&arr, i, minIndex);
	}
}